package 力扣.队列;

public class 设计循环队列622 {

}

/**
 * 方法一：引用变量used来区分空队列和满队列
 * 想象一下：front指针总是在rear指针的后面且指向元素，rear指针总是在元素的后一位
 * front = (front + 1) % max
 * rear = (rear - 1 + max) % max
 * 判断条件：队列为空：used = 0;
 *         队列为满：used = max
 * 取模运算：+-都必须取模
 */
class MyCircularQueue {
    private int []queue = null;//通过数组模拟循环队列
    private int front;//队首指针
    private int rear;//队尾指针（总是在队尾的后一位）
    private int used;//已经使用的空间
    private int max;//队列的最大空间
    // 参数k表示这个循环队列最多只能容纳k个元素
    public MyCircularQueue(int k){//初始化
        max = k;
        queue = new int[max];
    }
    // 将value放到队列中, 成功返回true
    public boolean enQueue(int value){
       if (isFull()){//判断非满
           return false;
       }
       queue[rear] = value;//rear指针的内容为空，可以放进元素
       rear = (rear + 1) % max;//rear指向队尾的后一个元素
       used++;//已用空间++
       return true;
    }
    // 删除队首元素，成功返回true
    public boolean deQueue(){
       if (isEmpty()){//判断非控
           return false;
       }
       int ret = queue[front];//取值（队首指针总是指向队首元素）
       front = (front + 1) % max;//删除（队首向前移动一个单位）
       used--;//已用空间--
       return true;
    }
    // 得到队首元素，如果为空，返回-1
    public int Front(){
        if (isEmpty()){//判断非空
            return -1;
        }
        return queue[front];//得到队首元素
    }
    // 得到队尾元素，如果队列为空，返回-1
    public int Rear(){
        if (isEmpty()){//判断非空
            return -1;
        }
        //由于rear在我们的'队尾元素的后面'，需要将'rear减1'
        int tail = (rear - 1 + max) % max;
        return queue[tail];
    }
    // 看一下循环队列是否为空
    public boolean isEmpty(){
        return used == 0;//已用空间为零
    }
    // 看一下循环队列是否已放满k个元素
    public boolean isFull(){
        return used == max;//已用空间等于最大空间
    }
}
/*
 方法二：多申请一个空间来判断空队列和满队列
 判断条件：队列为空：rear = front
         队列为满：（rear+1）% max = front
 */
class MyCircularQueue2{
    private int rear;
    private int front;
    private int max;
    private int[] queue;
    public MyCircularQueue2(int k) {
       max = k + 1;
       queue = new int[max];
    }
//   入队
    public boolean enQueue(int value) {
       if (isFull()){
           return false;
       }
       queue[rear] = value;
       rear = (rear + 1) % max;
       return true;
    }
//   出队
    public boolean deQueue() {
       if (isEmpty()){
           return false;
       }
       int ret = queue[front];
       front = (front + 1) % max;
       return true;
    }
//   查找队首元素
    public int Front() {
        if (isEmpty()){
            return -1;
        }
        return queue[front];
    }
//   查找队尾元素
    public int Rear() {
       if (isEmpty()){
           return -1;
       }
       int tail = (rear - 1 + max) % max;//加上 max 的原因：防止rear等于0 时，出现了 0-1 的情况
       return queue[tail];
    }
//   判断队列为空
    public boolean isEmpty() {
       return rear == front;
    }
//   判断队列是否为满（多申请了一个空间）
    public boolean isFull() {
       return (rear + 1) % max == front;
    }
}
